package main

import "fmt"

func main() {
	list := []int{1, 10, 2, 7, 3, 544, 67, 45, 7, 34, 56}
	result := mergeSort(list)
	for _, i := range result {
		fmt.Println(i)
	}

}

func mergeSort(list []int) []int {
	if len(list) < 2 {
		return list
	}
	mid := len(list)/2
	left := mergeSort(list[:mid])
	right := mergeSort(list[mid:])
	result := merge(left, right)
	return result
}

func merge(left, right []int) []int {
	leftIndex := 0
	rightIndex := 0
	result := []int{}
	for leftIndex < len(left) {
		if rightIndex == len(right) {
			result = append(result, left[leftIndex:]...)
			break
		}
		if left[leftIndex] <= right[rightIndex] {
			result = append(result, left[leftIndex])
			leftIndex++
		} else {
			result = append(result, right[rightIndex])
			rightIndex++
		}

	}
	result = append(result, right[rightIndex:]...)
	return result
}
